package algorithm.sort;

import java.util.Random;

public class QuickSort implements Sort {

    private Random random = new Random();
    @Override
    public String name() {
        return "快速排序";
    }

    @Override
    public void sort(Integer[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    //对区间[l,r]数组进行排序
    private void sort(Integer[] arr, int l, int r) {
        //说明之后一个元素，
        if (r-l<=7) {
            insertionSort(arr,l,r);
            return;
        }
        int p = partition(arr, l, r);
        sort(arr, l, p - 1);
        sort(arr, p + 1, r);
    }

    //寻找出下标p，使p左边的元素小于p，右边的元素大于p
    private int partition(Integer[] arr, int l, int r) {
        //stand 标准元素，使元素位于stand 2边
        int randomIndex = random.nextInt(r - l + 1) + l;
        swap(arr,randomIndex,l);
        int stand = arr[l];

        //  | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
        //  l              j                    i                               r
        //标准元素   [l+1,j]小于标准元素     [j+1,i-1]大于标准元素 i当前元素         边界
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i] < stand) {
                //与j+1交换位置
                swap(arr,i,j+1);
                j++;
            }
        }


        swap(arr,j,l);
        return j;
    }



    private void insertionSort(Integer[] arr, int l, int r){
        for (int i = l+1; i <=r; i++) {
            for (int j = i; j >l ; j--) {
                if (arr[j]<arr[j-1]){
                    int tmp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = tmp;
                }
            }
        }
    }



}
